/*
 * com.future CO.,ltd.
 */

package com.future;

import java.lang.*;
import java.util.*;

/**
 * Description: 567. �ַ���������
 * ���������ַ���?s1?��?s2 ��дһ���������ж� s2 �Ƿ���� s1?�����С�����ǣ����� true �����򣬷��� false ��
 * <p>
 * ���仰˵��s1 ������֮һ�� s2 �� �Ӵ� ��
 * <p>
 * ?
 * <p>
 * ʾ�� 1��
 * <p>
 * ���룺s1 = "ab" s2 = "eidbaooo"
 * �����true
 * ���ͣ�s2 ���� s1 ������֮һ ("ba").
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode-cn.com/problems/permutation-in-string
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @Author: future
 * @Date:2022/4/5:15:34
 */
public class Solution_567 {

    public static void main(String[] args) {
        String s1 = "ccaba";
        String s2 = "cccbabacbca";
        System.out.println(checkInclusion(s1, s2));
    }

    /**
     * ��������
     *
     * @param s1
     * @param s2
     * @return
     */
    public static boolean checkInclusion(String s1, String s2) {
        if (s1 == null || s1.length() == 0 || s2 == null || s2.length() == 0 || s1.length() > s2.length()) {
            return false;
        }
        char[] str1 = s1.toCharArray();
        int N = str1.length;
        char[] str2 = s2.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        // ��¼�ַ���Ƶ
        for (int i = 0; i < N; i++) {
            if (map.containsKey(str1[i])) {
                map.put(str1[i], map.get(str1[i]) + 1);
            } else {
                map.put(str1[i], 1);
            }
        }
        // ����ָ��
        int L = 0, allCharNum = N;
        // �����γɽ׶�
        for (int R = 0; R < N; R++) {
            if (map.containsKey(str2[R])) {
                int times = map.get(str2[R]);
                if (times > 0) {
                    allCharNum--;
                }
                map.put(str2[R], times - 1);
            }
        }
        for (int R = N; R < str2.length; R++) {
            if (allCharNum == 0) {
                return true;
            }
            char cha = str2[R];
            if (map.containsKey(cha)) {
                int times = map.get(cha);
                if (times > 0) {
                    allCharNum--;
                }
                map.put(cha, times - 1);
            }
            cha = str2[L++];
            if (map.containsKey(cha)) {
                int times = map.get(cha);
                if (times >= 0) {
                    allCharNum++;
                }
                map.put(cha, times + 1);
            }
        }
        if (allCharNum == 0) {
            return true;
        } else {
            return false;
        }
    }
}
